#ifndef KNAPSACK_H
#define KNAPSACK_H

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

// Structure to represent an item
typedef struct {
    int id;         // Item ID
    double weight;  // Weight of the item
    double value;   // Value of the item
} Item;

// Structure to store solution
typedef struct {
    int* selected;      // Array to store selected items (1 if selected, 0 if not)
    double total_value; // Total value of selected items
    double total_weight;// Total weight of selected items
} Solution;

// Function declarations
// Brute Force approach
Solution* bruteForce(Item* items, int n, double capacity);

// Dynamic Programming approach
Solution* dynamicProgramming(Item* items, int n, double capacity);

// Greedy approach
Solution* greedy(Item* items, int n, double capacity);

// Backtracking approach
Solution* backtracking(Item* items, int n, double capacity);

// Utility functions
void generateItems(Item* items, int n);
void printSolution(Solution* sol, Item* items, int n);
void freeSolution(Solution* sol);
void writeExecutionTime(const char* algorithm, int n, double capacity, double time_ms);
void writeFakeCode(const char* algorithm);

#endif 